package com.jyl.data.impl;

import com.jyl.data.Tree;

import java.util.function.Consumer;

/**
 * @ClassName BinarySearchTree
 * @Author admin
 * @Date 2024/6/12
 */
public class BinarySearchTree<E extends Comparable<E>> implements Tree<E> {

    private static class Node<E extends Comparable<E>> {
        E element;
        Node<E> leftChild;
        Node<E> rightChild;

        Node(E element, Node<E> leftChild, Node<E> rightChild) {
            this.element = element;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }
    }

    private int size;

    private Node<E> root;

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void add(E element) {
        if (root == null) {
            root = new Node<E>(element, null, null);
            size++;
            return;
        } else {
            Node<E> current = root;
            Node<E> pre = null;
            while (current != null) {
                if (element.compareTo(current.element) < 0) { // 左子树
                    pre = current;
                    current = current.leftChild;
                } else if (element.compareTo(current.element) > 0) { // 右子树
                    pre = current;
                    current = current.rightChild;
                } else {  // 找到目标节点
                    return;  // 终止循环并结束方法
                }
            }
            Node<E> targetNode = new Node<>(element, null, null);
            if (element.compareTo(pre.element) < 0) { // 将目标节点的父节点指向目标节点
                pre.leftChild = targetNode;
            } else {
                pre.rightChild = targetNode;
            }
        }
        size++;
    }

    @Override
    public E remove(E element) {
        Node<E> pre = new Node<>(null, root, null); // 创建虚拟节点，当目标节点是根节点时起作用
        // 1. 查找目标节点
        Node<E> current = root;
        while (current != null) {
            if (element.compareTo(current.element) < 0) {
                pre = current;
                current = current.leftChild;
            } else if (element.compareTo(current.element) > 0) {
                pre = current;
                current = current.rightChild;
            } else {
                break;
            }
        }

        if (current == null) { // 未找到目标节点
            return null;
        }

        // 2.1 目标节点是 叶子节点
        if (current.leftChild == null && current.rightChild == null) {
            if (pre.leftChild == current) {
                pre.leftChild = null;
            } else {
                pre.rightChild = null;
            }
            size--;
        } else if (current.leftChild == null || current.rightChild == null) { // 2.2 目标节点中包含一个叶子节点
            // 找到目标节点的叶子节点
            Node<E> targetChild = current.leftChild == null ? current.rightChild : current.leftChild;
            if (pre.leftChild == current) {
                pre.leftChild = targetChild; // 将目标节点的父节点指向目标节点的叶子节点
            } else {
                pre.rightChild = targetChild;
            }
            size--;
        } else { // 3 目标节点有中包含两个叶子节点 --> m1 取目标节点中右子树的最小值 , m2 取目标节点中左子树的最大值
            // 3.1 找到目标节点中 右子树的最小节点 , 并将其删除
            Node<E> minNode = current.rightChild;
            while (minNode.leftChild != null) {
                minNode = minNode.leftChild;
            }
            remove(minNode.element);

            // 3.2 将 minNode替换到目标节点的位置 --> 需要将 目标节点所指向的左子节点和右子节点 赋值给minNode
            minNode.leftChild = current.leftChild;
            minNode.rightChild = current.rightChild;

            // 3.3 需要将 (pre --> current) 转换为 (pre --> minNode)
            if (pre.leftChild == current) {
                pre.leftChild = minNode;
            } else {
                pre.rightChild = minNode;
            }
        }
        /*
        若目标节点是根节点，则还需要考虑root的指向(不然后续的 add,foreach都会受影响)，所有我们需要更新root的指向
         */
        if (pre.element == null) {
            /*
            问题1：如何理解赋值语句
                也就是把指向左子节点的地址赋值给了root，使得root也指向该地址
            问题2：为什么是 leftChild
                在虚拟节点定义的时候，虚拟节点的leftChild属性赋值的是root
             */
            root = pre.leftChild;
        }
        return element;
    }

    /*
     Pre-order Traversal 前序遍历: 根节点 --> 左子树 --> 右子树
     In-order Traversal 中序遍历: 左子树 --> 根节点 --> 右子树
     Post-order Traversal 后续遍历: 左子树 --> 右子树 --> 根节点
     */
    private void treeWalker(Node<E> node, Consumer<E> consumer, TRAVERSAL_ORDER order) {
        if (order == TRAVERSAL_ORDER.PRE) {
            if (node != null) {
                consumer.accept(node.element);
                treeWalker(node.leftChild, consumer, TRAVERSAL_ORDER.PRE);
                treeWalker(node.rightChild, consumer, TRAVERSAL_ORDER.PRE);
            }
        } else if (order == TRAVERSAL_ORDER.IN) {
            if (node != null) {
                treeWalker(node.leftChild, consumer, TRAVERSAL_ORDER.IN);
                consumer.accept(node.element);
                treeWalker(node.rightChild, consumer, TRAVERSAL_ORDER.IN);
            }
        } else {
            if (node != null) {
                treeWalker(node.leftChild, consumer, TRAVERSAL_ORDER.POST);
                treeWalker(node.rightChild, consumer, TRAVERSAL_ORDER.POST);
                consumer.accept(node.element);
            }
        }
    }

    @Override
    public void forEach(Consumer<E> consumer) {
        forEach(consumer, TRAVERSAL_ORDER.IN);
    }

    @Override
    public void forEach(Consumer<E> consumer, TRAVERSAL_ORDER order) {
        treeWalker(root, consumer, order);
    }


}
